import random


# 检测两个状态相等元素的个数
def check_state(state1, state2):
    sum = 0
    for i in range( 3 ):
        for j in range( 3 ):
            if state1[i][j] == state2[i][j]:
                sum += 1
    return sum  # 得到相等元素的个数


def h(state, target):
    # h(n)是n状态到目标状态的代价 每个状态有9个元素，所以h(n)的值为9-sum  sum = check_state(state, target)
    h = 9 - check_state( state, target )
    return h


# 初始态
# 初始化
state = [[2, 8, 3],
         [1, 6, 4],
         [7, 0, 5]]
# 记录0的坐标
x = 2
y = 1

# 末状态
target = [[1, 2, 3],
          [8, 0, 4],
          [7, 6, 5]]

len = 0


# 八数码
# 每个状态的结构：

# h(n)是n状态到目标状态的代价 每个状态有9个元素，所以h(n)的值为9-sum  sum = check_state(state, target)
# h()
# g(n)是n状态到父状态的代价  调用一次动作函数则加一
# f(n)就是g（n） + h(n)


class State:
    list = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    g = len  # 深度
    h = h( list, target )  # 代价（不再位的个数）
    f = g + h
    xy = [0, 0]  # 0的坐标
    prior = ""  # 父状态

    def set(self, x, y, state):
        self.list = state
        self.xy = [x, y]

    def getF(self):
        return self.f


# 定义open列表  最大深度为50
open = []  # 存储所有可能的状态
# 定义二维列表记录f值和在open中的位置
open_f = []

# 定义close列表
close = []  # 存储已经走过的状态


def finish():
    if state == target:
        return True
    else:
        return False


# 随机生成一个二维列表 其中字列表的元素为0-8  没有用到可以把初始状态设置为自动产生
def random_state():
    list = [1, 2, 3, 4, 5, 6, 7, 8]
    state = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    # 乱序排列list前8个元素
    random.shuffle( list )
    list.append( 0 )
    # 将list拆分为3个子列表
    for i in range( 3 ):
        state[i] = list[i * 3:i * 3 + 3]
    # 交换state中的state[2][2]元素到state[1][1]
    state[2][2] = state[1][1]
    state[1][1] = 0

    return state


# 打印状态
def print_state(state):
    for n in state:
        print( n )


# 判断动作的函数
def theSet(state, x, y):
    move = list()
    if x - 1 > -1:
        move.append( 'up' )
    if x + 1 < 3:
        move.append( 'down' )
    if y - 1 > -1:
        move.append( 'left' )
    if y + 1 < 3:
        move.append( 'right' )
    return move


# 生成子状态的函数
# 判断坐标x，y动作的函数
# 利用动作函数计算出所有的子集
def generate_state(state, x, y, move):  # State是类 x,y为0的坐标  move为动作
    # 创建一个新的状态集合
    new_state = []
    i = 0  # 子状态的个数

    if "up" in move and state.prior != "down":
        # 把state.list 拷贝到test 不改变state.list
        test = [row[:] for row in state.list]
        # 把test[x][y]和test[x-1][y]交换
        test[x][y], test[x - 1][y] = test[x - 1][y], test[x][y]
        # 把test添加到new_state[i].list中
        new_state.append( State() )
        new_state[i].set( x - 1, y, test )
        new_state[i].g = state.g + 1
        new_state[i].h = h( new_state[i].list, target )
        new_state[i].f = new_state[i].g + new_state[i].h
        new_state[i].prior = "up"

        i += 1

    if "down" in move and state.prior != "up":
        test = [row[:] for row in state.list]
        test[x][y], test[x + 1][y] = test[x + 1][y], test[x][y]
        new_state.append( State() )
        new_state[i].set( x + 1, y, test )
        new_state[i].g = state.g + 1
        new_state[i].h = h( new_state[i].list, target )
        new_state[i].f = new_state[i].g + new_state[i].h
        new_state[i].prior = "down"
        i += 1

    if "left" in move and state.prior != "right":
        test = [row[:] for row in state.list]
        test[x][y], test[x][y - 1] = test[x][y - 1], test[x][y]
        new_state.append( State() )
        new_state[i].set( x, y - 1, test )
        new_state[i].g = state.g + 1
        new_state[i].h = h( new_state[i].list, target )
        new_state[i].f = new_state[i].g + new_state[i].h
        new_state[i].prior = "left"
        i += 1

    if "right" in move and state.prior != "left":
        test = [row[:] for row in state.list]
        test[x][y], test[x][y + 1] = test[x][y + 1], test[x][y]
        new_state.append( State() )
        new_state[i].set( x, y + 1, test )
        new_state[i].g = state.g + 1
        new_state[i].h = h( new_state[i].list, target )
        new_state[i].f = new_state[i].g + new_state[i].h
        new_state[i].prior = "right"
        i += 1

    return new_state  # 返回一个子集 每个元素为一个状态  没有计算权值


# --------------------------------------------------------------
# begin开始：
print("初始状态：")
print_state( state )
print( "-----------------------------" )
i = 0  # 记录open写入的个数也是
open.append( State() )
open[i].set( x, y, state )  # 初始化
open_f.append( [open[i].f, i] )  # 初始化open_f  用于排序
i += 1
while True:
    close.append( (open[open_f[0][1]]) )  # 每次把open_f 的最代价写入close
    # 在open_f中删除该状态
    open_f.remove( open_f[0] )
    # 向op表中添加子状态
    # 每一个动产生的子集 放入open列表
    # 利用move得到新的状态，写入open表，并计算新状态的f值按照g值和h值和的大小排序
    move = theSet( close[len].list, close[len].xy[0], close[len].xy[1] )
    if move is []:
        print( "没有路径" )
        continue
    sub = generate_state( close[len], close[len].xy[0], close[len].xy[1], move )  # 得到子状态集合
    # 把sub中的元素添加到open表中# 将子状态写入open表中
    for n in sub:
        open.append( n )
        open_f.append( [open[i].f, i] )
        i += 1  # 每添加一个元素 i+1
    # 用open_f 每个元素的第一个子元素排序
    open_f.sort()
    len += 1
    # 退出条件
    if close[-1].list == target:
        print( "WIN" )
        print_state(close[-1].list)
        break
    if open_f == []:
        print( "LOSE" )
        break

path = []




def judge(state, x, y):

    test = [row[:] for row in state.list]
    if state.prior == "up":
        test[x][y], test[x + 1][y] = test[x + 1][y], test[x][y]  # down
        return test
    if state.prior == "down":
        test[x][y], test[x - 1][y] = test[x - 1][y], test[x][y]
        return test
    if state.prior == "left":
        test[x][y], test[x][y + 1] = test[x][y + 1], test[x][y]
        return test
    if state.prior == "right":
        test[x][y], test[x][y - 1] = test[x][y - 1], test[x][y]
        return test


# 倒序遍历node
# 判断正确的节点    后一个节点的xy位置和正确的节点的位置是相邻的
# 那个进行下一个动作的结果和下一个相同选哪个

path.append( close[-1] )


for x in range( len - 2, -1, -1 ):
    t = judge( path[-1], path[-1].xy[0], path[-1].xy[1] )
    if t == close[x].list:
        path.append( close[x] )


# 逆序列表
path.reverse()

print("最优路径：")
for n in path:
    print(n.prior,end=" ")
print("\n")
print("走过的节点数：" ,end=" ")
con = 0
for n in path:
    con +=1
print(con-1)
print("搜索过的节点数：" ,len)


print("最优过程：")
for n in path:
    print_state(n.list)
    print("--------------")

